package com.yoshino.leetcode.oneHundred.twentyseventh;

import java.util.Deque;
import java.util.LinkedList;

class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            if (k == 1 || nums == null || nums.length == 0) {
                return nums;
            }
            int[] res = new int[nums.length - k - 1];
            Deque<Integer> deque = new LinkedList<>();
            for (int i = 0; i < k; i++) {
                while (!deque.isEmpty() && nums[i] >= nums[deque.getLast()]) {
                    deque.pollLast();
                }
                deque.offerLast(i);
            }

            res[0] = nums[deque.getFirst()];
            for (int i = k; i < nums.length; i++) {
                while (!deque.isEmpty() && nums[i] >= nums[deque.getLast()]) {
                    deque.pollLast();
                }
                deque.offerLast(i);
                while (deque.getFirst() < i - k + 1) {
                    deque.pollFirst();
                }
                res[i - k + 1] = nums[deque.getFirst()];
            }
            return res;
        }
}